//
// Created by Win10 on 2022/11/15.
//
#include <iostream>
#include "b_tree.h"


using namespace std;

//--------------Stack--------------//
typedef struct LinkNode {
    BiTNode *data;
    struct LinkNode* next;
}*LiStack,LinkNode;

bool InitStack(LiStack& S);
bool StackEmpty(LiStack S);
bool Push(LiStack& S, BiTNode* x);
bool Pop(LiStack& S, BiTNode*& x);
bool GetTop(LiStack S, BiTNode*& x);
bool DestoryStack(LiStack& S);

bool InitStack(LiStack& S) {
    S = (LiStack)malloc(sizeof(LinkNode));
    if (S == NULL) return false;
    S->next = NULL;
    return true;
}

bool StackEmpty(LiStack S) {
    if (S->next == NULL) return true;
    return false;
}

bool Push(LiStack& S, BiTNode* x) {
    LinkNode* p;
    p = (LinkNode*)malloc(sizeof(LinkNode));
    if (p == NULL) return false;
    p->data = x;
    p->next = S->next;
    S->next = p;
    return true;
}

bool Pop(LiStack& S, BiTNode*& x) {
    if (StackEmpty(S)) return false;
    LinkNode* p = S->next;
    S->next = p->next;
    x = p->data;
    free(p);
    return true;
}

bool GetTop(LiStack S, BiTNode*& x) {
    if (StackEmpty(S)) return false;
    x = S->next->data;
    return true;
}

//--------------Queue--------------//
typedef struct {
    LinkNode* front, * rear;
}LinkQueue;

void InitQueue(LinkQueue& Q);
bool QueueEmpty(LinkQueue Q);
bool EnQueue(LinkQueue& Q, BiTNode* x);
bool DeQueue(LinkQueue& Q, BiTNode*& x);

void InitQueue(LinkQueue& Q) {
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

bool QueueEmpty(LinkQueue Q) {
    if (Q.front == Q.rear) return true;
    return false;
}

bool EnQueue(LinkQueue& Q, BiTNode* x) {
    LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = Q.rear->next;
    Q.rear->next = s;
    Q.rear = s;
    return true;
}

bool DeQueue(LinkQueue& Q, BiTNode*& x) {
    if (QueueEmpty(Q)) return false;
    LinkNode* q = Q.front->next;
    x = q->data;
    Q.front->next = q->next;
    if (Q.rear == q) {
        Q.rear = Q.front;
    }
    free(q);
    return true;
}

//--------------Binary Tree--------------//

bool InitBiTree(BiTree &T) {
    ElemType ch;
    cin >> ch;
    if (ch == '#') {
        T = nullptr;
    } else {
        T = (BiTNode *) malloc(sizeof(BiTNode));
        T->data = ch;
        InitBiTree(T->lchild);
        InitBiTree(T->rchild);
    }
}

void visit(BiTNode *p) {
    cout << p->data << " ";
}

//先序遍历（递归）
void PreOrder_Rec(BiTree T) {
    if (T == nullptr) return;
    visit(T);
    PreOrder_Rec(T->lchild);
    PreOrder_Rec(T->rchild);
}

//中序遍历（递归）
void InOrder_Rec(BiTree T) {
    if (T == nullptr) return;
    InOrder_Rec(T->lchild);
    visit(T);
    InOrder_Rec(T->rchild);
}

//后序遍历（递归）
void PostOrder_Rec(BiTree T) {
    if (T == nullptr) return;
    PostOrder_Rec(T->lchild);
    PostOrder_Rec(T->rchild);
    visit(T);
}
//先序遍历
void PostOrder(BiTree T){
    LiStack S;
    InitStack(S);
    BiTree p = T;
    BiTNode *r = NULL;   //辅助指针，指向最近访问的节点
    while(p||!StackEmpty(S)){
        if(p){                              //走到最左边
            Push(S,p);
            p = p->lchild;
        }else{                              //走到最右边
            GetTop(S,p);                    //读栈顶元素（非出栈）
            if(p->rchild&&p->rchild!=r){    //若右子树存在且未被访问过
                p = p->rchild;              //转向右
                Push(S,p);                  //压入栈
                p = p->lchild;              //再走到最左
            }else{                          //否则弹出栈顶元素并访问
                Pop(S,p);
                visit(p);
                r = p;                      //记录最近访问过的节点
                p = NULL;                   //节点访问完后重置p指针
            }
        }
    }
}
//中序遍历
void InOrder(BiTree T){
    LiStack S;
    InitStack(S);
    BiTree p = T;               //遍历指针
    while(p||!StackEmpty(S)){   //
        if(p){                  //一路向左
            Push(S,p);          //当前节点入栈
            p = p->lchild;      //左孩子不为空一直向左走
        }else{                  //出栈，并转向该节点的右孩子
            Pop(S,p);           //栈顶结点出栈，访问
            visit(p);
            p = p->rchild;      //向右子树走，
        }
    }
}
//后序遍历
void PreOrder(BiTree T){
    LiStack S;
    InitStack(S);
    BiTree p = T;               //遍历指针
    while(p||!StackEmpty(S)){   //
        if(p){                  //一路向左
            visit(p);
            Push(S,p);          //当前节点入栈
            p = p->lchild;      //左孩子不为空一直向左走
        }else{                  //出栈，并转向该节点的右孩子
            Pop(S,p);           //栈顶结点出栈
            p = p->rchild;      //向右子树走，
        }
    }
}
//层序遍历
void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(!QueueEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL){
            EnQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL){
            EnQueue(Q,p->rchild);
        }
    }
}
void test(){
    BiTree T;
    InitBiTree(T);
    cout<<"先序遍历（递归）"<<endl;
    PreOrder_Rec(T);
    cout<<endl;

    cout<<"中序序遍历（递归）"<<endl;
    InOrder_Rec(T);
    cout<<endl;

    cout<<"后序遍历（递归）"<<endl;
    PostOrder_Rec(T);
    cout<<endl;

    cout<<"先序遍历"<<endl;
    PreOrder(T);
    cout<<endl;

    cout<<"中序序遍历"<<endl;
    InOrder(T);
    cout<<endl;

    cout<<"后序遍历"<<endl;
    PostOrder(T);
    cout<<endl;

    cout<<"层序遍历"<<endl;
    LevelOrder(T);
    cout<<endl;
}

int main(){

    test();
    return 0;
}